三 Connection to Learning

verification possible if $E_{in}(h)$ small for fixed $h$

與學習間的對應

這部分看了很多次，但還是有點難以理解 bin model 和 learning 兩者對應的關係…所以可能會有誤。

用前面瓶子取彈珠的例子，來說明學習。

在瓶子中，我們不曉得的是 橘色的機率 。而在學習中，我們不曉得的是 target function ，所以我們自然無法知道在某一點時的 $f(x)$。
我們有興趣知道的是某個 $h(x)$ ，其結果是否與 $f(x)$ 一樣。

我們會有個 固定的 $h$ ，和專屬 $h$ 的瓶子。
這邊做個動作，從資料中，當 $h(x) = f(x)$ 兩者一樣時就把彈珠漆成 綠色，不一樣則為 橘色。 不需要知道 $f$ ，這就像是直接從原先瓶子裡取出幾個彈珠，來看是橘色還綠色一樣。

這樣的用意為何？ 如果從專屬 $h$ 的瓶子裡取出一把彈珠，就好比從資料中取出 $x_n$ 一樣。
我們檢查 $h$ 在資料中的表現怎麼樣， 也就是 在專屬 $h$ 的瓶子中 橘色彈珠的機率(不一樣則為 橘色)。
而在 bin model 中則為 取樣 size-N 的樣本，裡面橘色的機率

資料量夠大 => 抓一把夠多的彈珠
如同 bin model 中，藉由 sample 來推論 $\mu$；
學習中是利用 $h$ 在 已知資料 中的表現，來推論 $h(x)$ 和 $f(x)$ 的關係，目的就是要得知在 未知資料 中的表現狀況。(Hoeffding’s Inequality)

(i.i.d. = Independent and identically distributed random variables)

整個過程

我們有個機率，用於取樣產生資料，還有衡量 $h$ 和 $f$。 $h$ 是從 hypothesis set 中取出的一個。
我們可以利用產生出來的資料來說很多事(ex. $h$ 和 $f$ 的關係)

(虛線表示我們不知道)

$E_{out}$ 就是 整個瓶子，$h$ 和 $f$ 一不一樣，相當於 $\mu$。(我們不知道的)
$E_{in}$ 則是 取樣 出來的，相當於 $\nu$ ，可以拿來推論整個瓶子中，$h$ 和 $f$ 一不一樣。(我們知道的)

in 表示 in-sample ，反之則為 out 。

套進公式

把前面提到的 $\mu$ 和 $\nu$ 替換成 $E_{out}$ 和 $E_{in}$，分別為在 樣本外 的錯誤率和 樣本內 的錯誤率。
在 Hoeffding’s Inequality 下，如同前面所提，我們不需要知道 $f$ => $E_{out}$ ，就能利用 $E_{in}$ 推到 $E_{out}$。

結論則是: $E_{in}(h)$ 很小 => $E_{out}(h)$ 很小，這樣子的誤差推估。$h$ 和 $f$ 也就很接近。

驗證 h

但只有這樣不能算是學到東西，因為它是個固定的 $h$ ，是你強迫演算法去選它的。我們一切的推導，皆是發生在那個 $h$ 上， 但這樣子選得 $h$ 通常不會很好，所以得到的是 $g$ 和 $f$ 不接近。
($h$ 是 set 中的一個，$g$ 是選出來的那一個)

而真正的學習應該要能 挑選 $h$ ，而不是只會選某一個。所以這個過程只能算是 Verification ，驗證 $h$ 的誤差。

其流程長這樣:

我們的資料沒有經過 learning ，也不需要一個 hypothesis set 。

練習

得知了一個股票的規律，從過去 10 年的資料，抽樣 100 天來驗證這個規律，其中 80 天是符合的。
藉此我們能得知什麼？

四 Connection to Real Learning

learning possible if $\vert{H}\vert$ finite and $E_{in}(g)$ small

不好的資料

如果今天有很多個 $h$ 就代表著有很多瓶子，如果其中一個瓶子抓出來的彈珠皆是綠的 ( $h(x) = f(x)$ 才會漆成綠的)，要不要選它呢？

這邊的例子是擲硬幣，本來 1 個人全擲到正面的 機率很小，但 150 人中至少 1 人的機率卻 非常大。這就像是去選擇其中一個硬幣，來說這個硬幣比較特別。

本來 Hoeffding’s Inequality 告訴我們，樣本和母體得出來的 $E_{in}$ 和 $E_{out}$ ，相差很遠的機率很小，然而選擇這個動作卻 提高了不好的可能性。

老師留言:

獨立地拿每一顆硬幣丟十次，都會被原始的 Hoeffding 式子限制住。「獨立」 隨機的選擇一顆硬幣，並不會改變這個特性，但 「相依」 的選了個「最佳」硬幣，就會破壞掉這個特性了。

每次抓一把一把都可以看成取不同的資料，也就是不同的 $D_n$，而 Hoeffding 保證的是:　選得資料是 BAD 的機率很小(前面提到的公式)。也就是圖中下方格子裡填 BAD 的很少，下方數學式子則是把所有對 $h$ 是 BAD　的資料之機率加起來，結果會是很小的。

BAD 的資料就是 $E_{in}$ 和 $E_{out}$ 相差很多的。

　　

多個 h　　

我們必須確保演算法能自由自在地挑選 hypothesis ，所以不能有對某個 $h$ 時 $D$ 是 BAD 的情形發生，也就是圖中 $D_n$ 的某一直行，都必須不是 BAD。(圖中 1126)

然後現在我們想知道的是，對所有 hypothesis (M 個)，這個 BAD 資料發生的機率是多少？

可以說如果資料量夠大，就可以確保對所有挑出來的 $h$ ， $E_{in}(g)$ 和 $E_{out}(g)$ 是 PAC。
這樣就能說最合理的做法，就是選一個 $E_{in}(g)$ 為最小的， 幾乎可以確定$E_{out}(g)$ 也是最小的。

終於可以學習了　　

結論上來說，只要我們的　hypothesis　有限 (Ｍ 個)，Ｎ　足夠大，就能保證演算法能自由地挑選 $h$ 來當 $g$。
且挑出來的 $E_{in}(g)$ 和 $E_{out}(g)$ 接近，只要 $E_{in}(g)$ 非常小，$E_{out}(g)$ 也會非常小。

=> learning possible

圖中多的兩條虛線，有一個機率函數，右邊的是如何測試 $g$ 和 $f$ 接不接近，左邊的是如何產生資料。

　　

練習

如果某資料對 $h_1$ 是 BAD 的，$h_3$ 就只是 $h_1$ 的相反，其 $E_{in}$ 和 $E_{out}$ 仍會相差很多，也就是 BAD。

3 是原本 Hoeffding 式子推導出來的，而 4 則是 D 有重疊到的部分。